package LeetCode._02算法基础.day05滑动窗口;

import org.junit.Test;
import 题组.Solution;

import java.util.*;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 15 - 15:56
 * @Description 给定两个字符串s和 p，找到s中所有p的异位词的子串，
 * 返回这些子串的起始索引。不考虑答案输出的顺序。
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 * s 和 p 仅包含小写字母
 * @Version 中等
 */
public class _438找到字符串中所有字母异位词 {
    static String s = "cbaebabacd", p = "abc";

    @Test
    public void solve(){
        List<Integer> res = findAnagrams(s, p);
        System.out.println(res);
    }
    /*by me 滑动窗口*/
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()){
            return res;
        }

        int len = p.length();
        //统计s字符串中字母出现次数
        int[] count1 = new int[26];
        //统计p字符串中字母出现次数
        int[] count2 = new int[26];
        for(int i = 0; i < len; i++){
            count1[s.charAt(i) - 'a']++;
            count2[p.charAt(i) - 'a']++;
        }
        if(Arrays.equals(count1, count2)){
            res.add(0);
        }
        //i表示窗口的右端
        for(int i = len; i < s.length(); i++){
            count1[s.charAt(i) - 'a']++;
            count1[s.charAt(i - len) - 'a']--;
            if(Arrays.equals(count1, count2)){
                res.add(i - len + 1);
            }
        }
        return res;
    }
    /*官方思路*/
    //优化的滑动窗口

    /*

    我们不再分别统计滑动窗口和字符串 pp 中每种字母的数量，而是统计滑动窗口和字符串 pp 中每种字母数量的差
    并引入变量 differ 来记录当前窗口与字符串 pp 中数量不同的字母的个数，并在滑动窗口的过程中维护它。
    在判断滑动窗口中每种字母的数量与字符串 pp 中每种字母的数量是否相同时，只需要判断 differ 是否为零即可。

     */
    public List<Integer> findAnagrams1(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<>();
        }

        List<Integer> ans = new ArrayList<>();
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }
        //记录不同字符的类型个数
        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            //移除左端字符
            if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];
            //增加右端字符
            if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];

            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }

}
